package com.wenhao.leetcode.medium;

import java.util.ArrayList;
import java.util.List;

/**
 * 题目：https://leetcode-cn.com/problems/generate-parentheses/
 * 括号生成
 * @author Wenhao Tong
 * @create 2021-07-11 23:42
 */
public class LeetCode22 {
    public static void main(String[] args) {

    }

    public List<String> generateParenthesis(int n) {
        StringBuilder path = new StringBuilder();
        dfs(0,0,path,n);
        return result;
    }

    private List<String> result = new ArrayList<>();

    private void dfs (int left,int right,StringBuilder path,int n) {
        if (left == n && right == n) {
            result.add(path.toString());
            return;
        }
        // 逻辑就是当前面的左括号比右括号多的时候才可以添加右括号
        // 如果左括号和右括号一样多，那么此时只可以添加左括号
        // 如果一直保持这样的添加逻辑，不可能出现右括号比左括号多的情况，右括号比左括号多也就是没有意义的括号，类似于这样:())
        if (left < n) {
            path.append('(');
            dfs(left + 1,right,path,n);
            path.deleteCharAt(path.length() - 1);
        }
        if (left > right) {
            path.append(')');
            dfs(left,right + 1,path,n);
            path.deleteCharAt(path.length() - 1);
        }
    }
}
